package wwl.lsf;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/5/13
 * @Description
 */
public class 接雨水 {

    public int trap(int[] height) {
        int ans = 0;
        int size = height.length;
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) { //Search the left part for max bar size
                max_left = Math.max(max_left, height[j]);
            }
            for (int j = i; j < size; j++) { //Search the right part for max bar size
                max_right = Math.max(max_right, height[j]);
            }
            ans += Math.min(max_left, max_right) - height[i];
        }
        return ans;
    }


    public int getyushui(int[] height) {

        int size = height.length;

        int total = 0;

        for (int i = 1; i < size - 1; i++) {
            int maxLeft = 0;
            int maxRight = 0;

            for (int j = i; j >= 0; j--) {
                maxLeft = Math.max(maxLeft, height[j]);
            }
            for (int j = i; j < size; j++) {
                maxRight = Math.max(maxRight, height[j]);
            }

            total += Math.min(maxLeft, maxRight) - height[i];
        }

        return total;
    }

    public int dp(int height[]) {
        int result = 0;
        if (height == null || height.length == 0) {
            return result;
        }
        int size = height.length;
        int[] maxleft = new int[size];
        int[] maxRight = new int[size];
        maxleft[0] = height[0];

        for (int i = 1; i < size; i++) {
            maxleft[i] = Math.max(height[i], maxleft[i - 1]);
        }
        maxRight[size - 1] = height[size - 1];

        for (int i = size - 2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);
        }

        for (int i = 1; i < size - 1; i++) {
            result += Math.min(maxleft[i], maxRight[i]) - height[i];
        }


        return result;

    }

    public static int Linkedlisttrap(int[] height) {
        int ans = 0, current = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                ans += distance * bounded_height;
            }
            stack.push(current++);
        }
        return ans;
    }

    /**
     * 说下官方题解中双指针的理解，每次指针不动的那个位置就是当前遍历完所有数据的最大值，
     * 如right位置要比left位置值大，那么right位置就是当前遍历完所有数据的最大值。
     * 利用反证法证明，假如说最大值在right右边的m位置，那么能够从m位置向左移动到right位置，
     * 说明left左边有一个位置比m位置值更大，这显然违背m位置是最大值的假设，
     * 同理可以证明最大值在left左边的情况也不可能出现。
     *
     * 因此只要当heights[left] < heights[right]时，计算left位置的值时，，只需要用left_max-heights[left]即可，因为left_max是小于heights[right]的。
     * @param height
     * @return
     */
    public static int doublezhizhen(int[] height) {

        int result = 0;

        int left = 0;

        int right = height.length - 1;

        int leftMax = 0;
        int rightMax = 0;

        while (left < right) {

            if (height[left] < height[right]) {
                if (height[left] > leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] > rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;

            }
        }


        return result;

    }


    public static void main(String[] args) {
        int[] test = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        Arrays.sort(test);
        System.out.println(Linkedlisttrap(test));
        System.out.println(doublezhizhen(test));

    }
}
